﻿
namespace Mobwiz.SpellChecker.Core
{
    using System;
    using System.Linq;

    internal static class EditDistance
    {
        static int costOfDeletingSourceCharacter = ConfigurationEditDistance.COST_REMOVE_CHARS;
        static int costOfInsertingSourceCharacter = ConfigurationEditDistance.COST_INSERT_CHARS;
        static int costOfSubstitutingLetters = ConfigurationEditDistance.COST_REPLACE_CHARS;
        static int costOfSwappingLetters = ConfigurationEditDistance.COST_SWAP_CHARS;
        static int costOfChangingCase = ConfigurationEditDistance.COST_CHANGE_CASE;

        /// <summary>
        /// 获取2个单词之间的编辑距离
        /// </summary>
        /// <param name="word">原单词</param>
        /// <param name="similar">相似单词</param>
        /// <returns></returns>
        public static int GetDistance(string word, string similar)
        {
            return GetDistance(word, similar, null);
        }

        /// <summary>
        /// 获取2个单词之间的编辑距离
        /// </summary>
        /// <param name="word"></param>
        /// <param name="similar"></param>
        /// <param name="matrix"></param>
        /// <returns></returns>
        public static int GetDistance(string word, string similar, int[][] matrix)
        {
            //Allocate memory outside of the loops. 
            int i;
            int j;
            int costOfSubst;
            int costOfSwap;
            int costOfDelete;
            int costOfInsertion;
            int costOfCaseChange;

            bool isSwap;
            char sourceChar = (char)0;
            char otherChar = (char)0;

            int a_size = word.Length + 1; // 原词长度
            int b_size = similar.Length + 1; // 相似的词的长度


            //Only allocate new memory if we need a bigger matrix. 
            if (matrix == null || matrix.Count() < a_size || matrix[0].Count() < b_size)
            {
                matrix = new int[a_size][];
                for (int k = 0; k < matrix.Count(); k++)
                {
                    matrix[k] = new int[b_size];
                }
            }

            matrix[0][0] = 0;

            // |
            // |
            // V
            for (i = 1; i != a_size; ++i)
                matrix[i][0] = matrix[i - 1][0] + costOfInsertingSourceCharacter; //initialize the first column
            // ---->
            for (j = 1; j != b_size; ++j)
                matrix[0][j] = matrix[0][j - 1] + costOfDeletingSourceCharacter; //initalize the first row

            for (i = 1; i != a_size; ++i)
            {
                sourceChar = word.ToCharArray()[i - 1];   // 原单词中的第一个字母开始
                for (j = 1; j != b_size; ++j)
                {

                    otherChar = similar.ToCharArray()[j - 1]; // 原单词中的第一个字母开始
                    if (sourceChar == otherChar)
                    {   // 如果相同，不用变换，直接将cost代入下一步
                        matrix[i][j] = matrix[i - 1][j - 1]; //no change required, so just carry the current cost up
                        continue;
                    }

                    //替换代价
                    costOfSubst = costOfSubstitutingLetters + matrix[i - 1][j - 1];
                    //if needed, add up the cost of doing a swap
                    costOfSwap = int.MaxValue;

                    //判断是否交换
                    // 两个单词都不是第一个字母 && 原单词中本次循环中的字母 等于 相似单词中的本次循环的上一个字母 && 原单词中本次循环的上一个字母等于本次循环中的字母
                    isSwap = (i != 1) && (j != 1) && sourceChar == similar.ToCharArray()[j - 2] && word.ToCharArray()[i - 2] == otherChar;
                    if (isSwap)
                        costOfSwap = costOfSwappingLetters + matrix[i - 2][j - 2]; //交换字母的循环cost要从上上个算。。

                    costOfDelete = costOfDeletingSourceCharacter + matrix[i][j - 1]; //删除要从上一列
                    costOfInsertion = costOfInsertingSourceCharacter + matrix[i - 1][j]; // 插入要从上一行

                    costOfCaseChange = int.MaxValue; //大小写的cost如此之大 - -##
                    // 如果忽略大小写，两个字母一样
                    if (equalIgnoreCase(sourceChar, otherChar))
                        costOfCaseChange = costOfChangingCase + matrix[i - 1][j - 1];
                    //选取一个最小的cost
                    matrix[i][j] = minimum(costOfSubst, costOfSwap, costOfDelete, costOfInsertion, costOfCaseChange);
                }
            }

            return matrix[a_size - 1][b_size - 1]; // matrix的最后一个值就是ED返回之
        }

        /// <summary>
        /// 忽略大小写比较2个字符
        /// </summary>
        /// <param name="ch1"></param>
        /// <param name="ch2"></param>
        /// <returns></returns>
        private static bool equalIgnoreCase(char ch1, char ch2)
        {
            if (ch1 == ch2)
            {
                return true;
            }
            else
            {
                return (Char.ToLower(ch1) == char.ToLower(ch2));
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <param name="c"></param>
        /// <param name="d"></param>
        /// <param name="e"></param>
        /// <returns></returns>
        static private int minimum(int a, int b, int c, int d, int e)
        {
            int mi = a;
            if (b < mi)
                mi = b;
            if (c < mi)
                mi = c;
            if (d < mi)
                mi = d;
            if (e < mi)
                mi = e;

            return mi;
        }
    }
}
